package mashibing.class6;

import util.MathUtil;

/**
 * 堆
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-03-27
 */
public class Class6_2_Heap {

    // 大根堆(完全二叉树，所有子树都比root节点小)
    public static class MyMaxHeap {
        public int size = 0;
        public int[] heapArray = new int[100];

        public void add(int ele) {
            int index = size;
            heapArray[index] = ele;
            int parentIndex = (index - 1) / 2;
            while (heapArray[parentIndex] < heapArray[index]) {
                MathUtil.swap(heapArray, parentIndex, index);
                index = parentIndex;
                parentIndex = (index - 1) / 2;
            }
            size++;
        }

        public int pop() {
            if (size == 0) {
                return -1;
            }
            int result = heapArray[0];
            heapArray[0] = heapArray[--size];
            int index = 0;
            int left = 1;
            while (left < size) {
                int larges = left < size - 1 ? (heapArray[left] < heapArray[left + 1] ? left + 1 : left) : left;
                if (heapArray[index] >= heapArray[larges]) {
                    break;
                }
                MathUtil.swap(heapArray, index, larges);
                index = larges;
                left = 2 * index + 1;
            }
            return result;
        }

        public void printHeap() {
            for (int i = 0; i < size; i++) {
                System.out.print(heapArray[i]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        MyMaxHeap myMaxHeap = new MyMaxHeap();
        myMaxHeap.add(4);
        myMaxHeap.add(7);
        myMaxHeap.add(1);
        myMaxHeap.add(5);
        myMaxHeap.printHeap();
        System.out.println("-------------------------");
        System.out.println(myMaxHeap.pop());
        System.out.println("-------------------------");
        myMaxHeap.printHeap();
    }

}
